package history

// 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
// 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
func findMinCoverStr(s, t string) string {
	if len(s) < len(t) {
		return ""
	}
	if s == t {
		return s
	}
	var needMap = make(map[byte]int)
	for i := 0; i < len(t); i++ {
		needMap[t[i]]++
	}
	var needCnt = len(t)
	var resLeft = -1
	var resRight = len(s)
	var left = 0
	var right = 0
	for right < len(s) {
		if needMap[s[right]] > 0 {
			needCnt--
		}
		needMap[s[right]]--
		if needCnt == 0 {
			for needMap[s[left]] != 0 {
				needMap[s[left]]++
				left++
			}
			if right-left < resRight-resLeft {
				resRight = right
				resLeft = left
			}
			needMap[s[left]]++
			left++
			needCnt++
		}
		right++
	}
	if resLeft == -1 {
		return ""
	}
	return s[resLeft : resRight+1]
}
